数组、切片和映射

Author Avatar
子语 2018 - 01 - 17
  • 在其它设备中阅读本文章

数组、切片和映射

数组的内部实现和基本功能

数组是切片和映射的基础数据结构。

内部实现

在Go中，数组是一个长度固定的数据类型，用于存储一段具有相同类型的元素的连续块。存储的数据类型可以是内置的，如整型，也可以是某种结构类型。数组的每个元素都紧邻着下一个元素，可以通过索引来访问。

数据占用的内存是连续分配的，因此CPU能把正在使用的数据缓存更久的时间，同时内存连续很容易计算索引，可以快速迭代数组里的所有元素。数组的元素类型相同，且连续分配，就可以以固定速度索引数组中的任意数据，速度非常快。

声明和初始化

声明数组时需要指定内部存储的数据类型以及长度。一旦声明，数据里存储的数据类型和长度就不能改变。如果要存储更多元素，就需要创建一个更长的数组，将源数组的值复制过去。数组初始化时，会将每个元素初始化为对应类型的零值。

package main

import "fmt"

func main()  {
	// 声明一个长度为5的数组
	var array1 [5]int
	// 声明一个长度为5的数组并用具体值初始化每个元素
	array2 := [5]int{10, 20, 30,40, 50}
	// 让Go自动那个计算声明的数组长度
	array3 := [...]int{10, 20, 30, 40, 50}
	// 指定特定元素的值，index:value，指定索引为index的元素值为value
	array4 := [5]int{1: 10, 2: 20}
    // for循环输出语句
	for index, value := range array4{
		fmt.Printf("arr[%d] = %d \n", index, value)
	}

	fmt.Println(len(array1)) // 5
	fmt.Println(len(array2)) // 5
	fmt.Println(len(array3)) // 5
}

使用数组

要访问数组时，可以利用[]运算符，通过索引访问元素。

package main

import "fmt"

func main()  {
	/* 使用索引访问数组元素 */
	array := [5]int {10, 20, 30, 40, 50}
	// 修改索引为2的元素的值
	array[2] = 35

	/* 声明一个元素都是指针的数组，使用*运算符就能访问元素指针所指向的值 */
	array1 := [5]*int{0: new(int), 1: new(int)}
	*array1[0] = 10
	*array1[1] = 20

	/* 将同类型的数组赋值给另一个数组,类型相同指的是数据类型和长度都相等 */
	colorArray := [5]string{"Blue", "Red", "Green", "Yellow", "Pink"}
	var colorArray1 [5]string
	colorArray1 = colorArray
	for _, value := range colorArray1{
		fmt.Println(value)
	}

	/* 编译器会阻止不同类型的数组互相赋值 */
	var stringarray [5]string
	var shortarray [4]int
	var longarray [6]int
	intarray := [5]int{1, 2, 3, 4, 5}
	// 类型不同的数组不能互相赋值
	stringarray = intarray
	// 不能将长数组赋值给短数组
	shortarray = intarray
	// 不能将短数组赋值给长数组
	longarray = intarray

	/* 把一个指针数组赋值给另一个 */
	var array3 [3]*string
	array4 := [3]*string{new(string), new(string), new(string)}
	*array4[0] = "Red"
	*array4[1] = "Blue"
	*array4[2] = "Green"
	array3 = array4
	for _, value := range array3{
		fmt.Println(value)
	}
}

多维数组

package main

func main()  {
	/* 声明一个二维数组 */
	var a1 [4][2] int
	a2 := [4][2]int{ {10, 11}, {12, 13}, {14, 15}, {16, 17} }
	
	/* 声明数组并初始化外层索引为1和3的元素 */
	a3 := [4][2]int{ 1: {20, 21}, 3: {40, 41}}
	
	/* 声明数组并初始化外层数组和内层数组的单个元素 */
	a4 := [4][2]int{ 1: {0: 20}, 3: {1: 41}}
	
	/* 访问数组中的元素 */
	a1[0][0] = 10
	
	/* 同类型数组可以互相赋值，此处的同类型指的是长度，数据类型相同 */
	a1 = a2
	
	/* 使用索引为多维数组赋值*/
	// 将数组a1中索引为1的值复制到一个同类型数组中
	var a5 [2]int = a1[1]
	
	// 将数组a1中外层索引为1，内层索引为0的元素赋予变量
	var value int = a1[1][0]
	
}

在函数间传递数组

从内存和性能来看，在函数间传递数组是一个开销很大的操作，因为不论数组多长，都会被完整的复制并传递给函数。假设现在有一个int型数组长度为100万，在64位架构上需要8MB的内存。

package main

func main()  {
	
	var array [1e6]int
	foo(array)
	
}

// 函数foo接收一个长度为100万的数组
func foo(array [1e6]int) {
	
}

每次foo被调用时，必须在栈上分配8MB的内存。之后，整数组的值被复制到刚分配的内存中。这开销十分的大。我们可以通过只传入指向数组的指针的方式解决这个问题。这样只需要复制8字节的数据而不需要复制8MB的数据到栈上，。

package main

func main()  {

	var array [1e6]int
	// 将array的地址传给foo
	foo(&array)

}

// 函数foo接收一个指向长度为100万的数组的指针
func foo(array *[1e6]int) {

}

这样操作会更有效地利用内存，性能也更好。但由于传递的是指针，所以如果改变指针指向的值，会改变共享的内存。切片能更好地处理这类共享问题。

切片的内部实现和基础功能

切片是一种数据结构，便于使用和管理数据集合。切片是围绕动态数组的概念构建的，可以自动增长和缩小。切片的动态增长是通过函数append实现的。还可以通过对切片再次切片来缩小一个切片的大小。因为切片的底层内存也是在连续块中分配的，所以切片还能取得索引，迭代以及为垃圾回收优化的好处。

内部实现

切片是很小的对象，对底层数组进行抽象，并提供相关的操作方法。切片有3个字段的数据结构，这三个字段分别是指向底层数组的指针，切片访问的元素的个数（即长度）和切片允许增长的到的元素个数（即容量）。

创建和初始化

是否能提前知道切片需要的容量通常会决定要如何创建切片。

make和切片字面量
package main

func main()  {

	/* 创建一个字符串切片，长度和容量都是5 */
	slice := make([]string, 5)

	/* 创建一个长度为3，容量为5的字符串切片 */
	s1 := make([]string, 3, 5)
  
    /* 创建长度和容量都是5的切片 */
    s2 := []string {"Red", "Blue", "Green", "Yellow", "Pink"}
  
    /* 创建chang*/

}

上述切片可以访问3个元素，而底层数组拥有5个元素，剩下2个元素可以后期操作合并到切片，并通过切片访问这些元素。如果基于这个切片创建新的切片，新切片会和原有切片共享底层数组，也能通过后期操作访问多余容量的元素。

package main

import "fmt"

func main()  {

   /* 切片的容量不能小于长度 */
   slice := make([]string, 5, 3)
   
   // Error:len larger than cap in make([]string)

   fmt.Println(slice)

}

如果在[]元素符中指定了值，那么创建的就是数组而不是切片。

package main

import "fmt"

func main()  {

   /* 声明长度和容量皆为100的切片 */
   slice := []string{99:"Red"}

   /* 声明长度为100的数组 */
   s1 := [100]string{99:"Red"}
   fmt.Println(s1)
   fmt.Println(slice)

}
nil和空切片

nil切片常用于描述一个不存在的切片，例如当函数要求返回一个切片但返回异常时。而空切片在底层数组包含0个元素，也没有分配任何存储空间，可用于当数据库查询返回0个结果时。

package main

import "fmt"

func main()  {

   /* nil切片，指针为nil */
   var slice []int
   
   /* 空切片，指针为空 */
   s1 := make([]int, 0)
   s2 := []int{}

}

使用切片

  • 赋值和切片

对于切片中某个索引指向的元素赋值和数据操作一致。

package main

func main()  {

   // 创建长度和容量都是5的切片
   slice := []int{10, 20, 30, 40, 50}
   
   // 修改索引为0的元素
   slice[0] = 0

}

切片之所以被称为切片，是因为创建一个新切片就是把底层数组切出一部分。

package main

import "fmt"

func main()  {

	slice := []int{10, 20, 30, 40, 50}

	for i := 0; i < len(slice) ; i++ {
		fmt.Println(slice[i]) // 10, 20, 30, 40, 50
	}

	// 创建一个新切片，长度为2，容量为4
	newSlice := slice[1:3]

	for i := 0; i < len(newSlice) ; i++ {
		fmt.Println(newSlice[i]) // 20 30
	}
}

无法加载

上述结果显示，两个切片共享同一段底层数组，但是不同的切片看到的是数组的不同部分。对于底层数组容量为k的lices[i:j]，新切片的长度为j-i,容量为k-i。

此时两个数组共享同一个底层数组，如果一个切片修改了底层数组的共享部分，另一个切片也能感受到。

package main

import "fmt"

func main()  {

   slice := []int{10, 20, 30, 40, 50}

   newSlice := slice[1:3]
   // 修改新切片索引为1的元素
   newSlice[1] = 35

   for i := 0; i < len(slice) ; i++ {
      fmt.Println(slice[i]) // 10, 20, 35, 40, 50
   }
}

修改newSlice索引为1的元素其实也是修改了slice索引为2的元素。

切片只能访问其长度内的元素。与切片容量相关联的元素只能用于增长元素，在使用这部分元素前，必须将其合并到切片的长度里。

package main

import "fmt"

func main()  {

   slice := []int{10, 20, 30, 40, 50}

   newSlice := slice[1:3]
   
   // newSlice长度为2，所以索引为3的元素对其而言不存在
   newSlice[3] = 35
   // Error：runtime error: index out of range

   for i := 0; i < len(slice) ; i++ {
      fmt.Println(slice[i]) // 10, 20, 35, 40, 50
   }
}

切片有额外的容量很好，但如果没有把这些容量合并到切片的长度中，这些容量就是没用的。

  • 切片增长

    切片可以按需增长容量，Go中的append函数会处理增长长度的所有操作细节。要使用append需要一个被操作的切片和一个要追加的值。

    package main

import "fmt"

func main()  {

   slice := []int{10, 20, 30, 40, 50}

   newSlice := slice[1:3]

   // 使用原有的容量来分配一个新元素
   newSlice = append(newSlice, 60)

   for i := 0; i < len(slice); i++ {
      fmt.Println(slice[i]) // 10 20 30 40 50 
   }
}

newSlice在底层数组还有可用容量，因此append会将可用元素合并到切片的长度中，并对其赋值。但由于和slice共享同一个数组，所以slice中索引为3的元素也会被改变。

如果切片的底层数组没有可用容量，append会创建一个新的数组，将被引用的现有的值复制到新数组中，再追加新的值。

package main

import "fmt"

func main()  {

   slice := []int{10, 20, 30, 40}

   newSlice := append(slice, 50)

   for i := 0; i < len(slice); i++ {
      fmt.Println(slice[i]) // 10 20 30 40
   }

   for i := 0; i < len(newSlice); i++ {
      fmt.Println(newSlice[i]) // 10 20 30 40 50
   }
   
}

append会智能处理底层数组的容量增长，当切片容量小于1000时，会成倍增长容量。但超过1000时，会将增长因子设为1.25.

  • 创建切片时的3个索引
package main

import "fmt"

func main()  {

	source := []int{10, 20, 30, 40, 50}

    // 定义一个长度为1，容量为2的切片
    // 2为新切片开始的索引
    // 3为新切片的长度+2
    // 4为新切片的容量+2
	slice := source[2:3:4]

	for i := 0; i < len(slice); i++ {
		fmt.Println(slice[i]) // 30
	}

	for i := 0; i < len(source); i++ {
		fmt.Println(source[i]) // 10 20 30 40 50
	}
}

此时切片的长度，对于slice[i:j:k]，其长度为j-i，容量为k-i.如果设置的容量比可用容量大，就会运行出错。

package main

func main()  {
   source := []int{10, 20, 30, 40, 50}
   slice := source[2:3:6]
   // panic: runtime error: slice bounds out of range
  
}

append会先使用可用容量，如果没有可用容量就会创建新的底层数组。这导致很容易忘记切片间正在共享一个数组，一旦发生这种情况，会导致问题，对切片内容的修改会影响多个切片。

因此设置长度和容量一样的好处就是，会强制让新的切片的第一个append操作创建一个新的底层数组，与原有的数组分离。

package main

import "fmt"

func main()  {

   source := []int{10, 20, 30, 40, 50}

   slice := []int{60, 70}

   // 将两个切片追加。source追加slice元素
   fmt.Printf("%v\n", append(source, slice...)) // [10 20 30 40 50 60 70]

   for i := 0; i < len(source); i++ {
      fmt.Println(source[i]) // 10 20 30 40 50
   }

}
  • 迭代切片

切片是一个集合，可以迭代其中的元素。Go可以使用关键字range配合关键字for迭代切片里的元素。

package main

import "fmt"

func main()  {

   source := []int{10, 20, 30, 40, 50}

   for index, value := range source {
      fmt.Printf("index = %d, value = %d \n", index, value)
   }

}

迭代切片时，关键字range会返回两个值，一个是当前元素的索引，一个是当前元素值的一个副本。此处要注意的是，切片返回的是元素值的副本，不是对该元素的直接引用。

package main

import "fmt"

func main()  {

   source := []int{10, 20, 30, 40, 50}
   
   for index, value := range source {
      fmt.Printf("Value: %d Value-Addr: %X ElemAddr: %X \n", value, &value,
         &source[index])
   }
   
   /** Output
   Value: 10 Value-Addr: C04204A088 ElemAddr: C042066030 
   Value: 20 Value-Addr: C04204A088 ElemAddr: C042066038 
   Value: 30 Value-Addr: C04204A088 ElemAddr: C042066040 
   Value: 40 Value-Addr: C04204A088 ElemAddr: C042066048 
   Value: 50 Value-Addr: C04204A088 ElemAddr: C042066050 
    */
}

此时我们可以看到副本的地址一直是不变的是因为迭代返回的变量是在迭代过程中根据切片依次赋予的新值，但其本身不变。要想获取元素真正的地址，需要使用切片变量和索引值。

range的迭代是从切片索引0开始的，要像从其他索引开始迭代，可以使用for循环。

package main

import "fmt"

func main()  {

   source := []int{10, 20, 30, 40, 50}

   // 从索引2开始迭代切片
   for index := 2; index < len(source); index ++ {
      fmt.Printf("value = %d, index = %d \n", source[index], index)
   }

}

Go中有两个内置函数len()和cap()，可以用于处理数组、切片和通道。对于切片，len()返回切片的长度，cap()返回切片的容量。

package main

import "fmt"

func main()  {

   source := []int{10, 20, 30, 40, 50}

   slice := append(source, 60)

    // 当append超出原切片容量时，会创建新数组，且当元素为1000时，容量会翻倍
   fmt.Println(cap(slice)) // 10
}

多维切片

package main

import "fmt"

func main()  {

   // 创建多维切片，该切片中包含两个切片{10},{10, 20}
   slice := [][]int{ {10}, {10, 20}} 
   fmt.Println(slice) // [[10] [10 20]]
   // 为切片中的第一个切片追加值为20的元素
   slice[0] = append(slice[0], 20)
   fmt.Println(slice) // [[10 20] [10 20]]
}

多维切片append的过程是先增长{10}，然后将增长后的{10, 20}赋值给slice[0]。多维切片，操作时会涉及众多布局和值，但是切片本身结构简单，可以以很小的成本在函数间传递。

切片在函数间传递

切片的尺寸小，在函数间赋值和传递切片的成本也低。

package main

func main() {

   slice := make([]int, 1e6)
   foo(slice)
}

func foo(slice []int) []int {
   return slice
}

在64位架构的机器上，一个切片需要24字节的内存：指针字段需要8字节，长度和容量字段分别需要8字节。由于切片关联的数据包含在底层数组中，不属于切片本身，所以将切片复制到任何函数时，对底层数组大小都不会有影响。复制的只是切片本身，不会涉及底层数组 。

映射的内部实现和基本功能

映射是一种数据结构，用于存储一系列的键值对。映射里基于键来存储值。映射的优势是，能够基于键快速检索数据，键就像是索引一样，指向与该键关联的值。

内部实现

映射是一个集合，可以使用类似切片的方式迭代映射中的元素。但映射是无序集合，这使得无法预测键值对被返回的顺序，即使用同样的顺序保存键值对，但每次迭代映射的时候，顺序也会不一样。这是因为映射的实现使用了散列表。散列表的具体细节暂时不描述。

创建和初始化

package main

import "fmt"

func main() {

   // 创建一个键值类型都是string的映射
   dict1 := make(map[string]string)
   
   fmt.Println(dict1)

   // 创建一个映射，key为int,value为string
   dict := map[int]string{1:"One",2:"Two",3:"Three"}
   // 迭代循环，由结果可得，其是无序集合，每次输出的顺序可能都不一样
   for key, value := range dict {
      fmt.Printf("%d = %s \n", key, value)
   }
}

映射的长度会根据初始化时指定的键值对数量来确定。映射的键可以是任何只，可以是基本数据类型，也可以是结构类型，只要这个值可以用==运算符做比较。切片、函数以及包含切片的结构类型由于使用了引用，都不能作为映射的键。但可以作为映射的值。

package main

import "fmt"

func main() {

   // 将切片作为映射的键
   dict1 := map[[]string] int{}
   // Exception: invalid map key type []string
   fmt.Println(dict1)
   // 将切片作为映射的值
   dict2 := map[int] []string{}
   fmt.Println(dict2)
}

使用映射

键值对赋值给映射，是通过指定适当类型的键并给这个键赋值来完成的。

package main

func main() {
   //  声明一个空映射
   nums := map[string]string{}

   // 将"1"对应的英文"One"加入到映射中
   nums["1"] = "One"

   // 空映射可以用于存储键值对，但nil映射不能
   var colors map[string]string

   colors["Red"] = "#da1337"
   // panic: assignment to entry in nil map


}

检测映射中是否存在某个键是映射的常用操作。这个操作允许用户写一些逻辑来确定是否完成了某个操作或是否在映射中缓存了特定数据，也可以用于比较两个映射，来确定哪些键值对互相匹配。

package main

import "fmt"

func main() {
   //  声明一个空映射
   nums := map[string]string{}

   // 将"1"对应的英文"One"加入到映射中
   nums["1"] = "One"

   // 同时获取映射中key对应的值，以及这个键是否存在
   value, exists := nums["1"]
   if exists {
      fmt.Println(value)
   }
    
   // 只返回键对应的值，从而判断这个值是不是零值，以此来判断key是否存在
   v := nums["1"]
   if v != "" {
      fmt.Println(value)
   }

}

Go中即使键不存在，也会返回一个值。这个值是值对应的数据类型的零值。

可以使用delete()函数删除映射中的键值对

package main

import "fmt"

func main() {
   //  声明一个空映射
   nums := map[string]string{
      "1": "One",
      "2": "Two",
      "3": "Three",
   }

   delete(nums, "2")

   for key, value := range nums {
      fmt.Printf("%s = %s \n", key, value)
   }

}

在函数间传递映射

在函数间传递映射时，并不会造出该映射的副本，即将映射传递给函数后，所有对这个映射的映射都会收到函数的操作带来的影响。

package main

import "fmt"

func main() {
   //  声明一个空映射
   nums := map[string]string{
      "1": "One",
      "2": "Two",
      "3": "Three",
   }

   for key, value := range nums {
      fmt.Printf("%s = %s \n", key, value)
      // Output:
      // 1 = One 
      // 2 = Two
      // 3 = Three 
   }

   remove(nums, "2")

   for key, value := range nums {
      fmt.Printf("%s = %s \n", key, value) 
      // Output:
      // 1 = One 
      // 3 = Three 
   }
}

func remove(dict map[string]string, key string)  {
   delete(dict, key)
}

This blog is under a CC BY-NC-SA 3.0 Unported License
本文链接：http://yov.oschina.io/article/Go/Go Base/数组、切片和映射/